package graphs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class BFS {

	static class Node {

		int value;
		List<Node> list = new LinkedList<Node>();

		public Node(int v) {
			this.value = v;
		}
		
		public void add(Node n) {
			this.list.add(n);
		}
		
		public List<Node> getNodes() {
			return list;
		}
	}

	public static void main(String[] args) {

		System.out.println("DFASFDSA");
		
		Node n1 = new Node(8);
		Node n2 = new Node(15);
		Node n3 = new Node(9);
		Node n4 = new Node(19);
		Node n5 = new Node(44);
		Node n6 = new Node(0);
		Node n7 = new Node(12);
		Node n8 = new Node(34);
		Node n9 = new Node(76);
		
		n1.add(n2);
		n1.add(n3);
		n1.add(n5);
		n1.add(n8);
		n1.add(n9);
		n2.add(n4);
		n2.add(n7);
		n3.add(n5);
		n4.add(n1);
		n4.add(n3);
		n5.add(n2);
		n7.add(n6);
		
		doBFS(n1);

	}

	private static void doBFS(Node node) {
		if (node == null) {
			return;
		}
		Set<Node> set = new HashSet<Node>();
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(node);
		set.add(node);
		
		while (!queue.isEmpty()) {
			node = queue.poll();
			System.out.println(node.value);
			for (Node n : node.getNodes()) {
				if (!set.contains(n)) {
					queue.offer(n);	
					set.add(n);
				}
			}
		}
	}

}
